// 解题思路：
// 求解二叉树的最大路径和，需要后续遍历二叉树的所有节点，求解以每一个节点为根节点的最大路径和
// 最终的最长路径肯定是以某个节点为根节点的最大路径
// 有可能是 根节点，也有可能是 根 + 左子树，也有可能是 根 + 右子树，也有可能是 根 + 左子树 + 右子树
// 要结合根节点求解最大路径和，就需要计算左子数单链表的最大和以及右子树单链表的最大和
// 再结合根节点进行整合，返回最大单链和
// 每次返回之前都要收集下信息，有可能某一棵子数就已经是最终结果了

// 技巧：
// 左子树求出来有可能是负的，为了简化代码，可以先让它和 0 取一个最大值
// 同理右子树也和 0 取最大值

public class MaxPathSum {
    public int ret = Integer.MIN_VALUE;
    public int maxPathSum (TreeNode root) {
        dfs(root);
        return ret;
    }
    public int dfs(TreeNode root){
        if(root == null) return 0;
        int left = Math.max(0, dfs(root.left));
        int right = Math.max(0, dfs(root.right));
        ret = Math.max(ret, root.val + left + right);
        return root.val + Math.max(left, right);
    }
}
